package backtracking;

import java.util.Scanner;

/**
 * 
 * @author victor
 * 
 */
public class PartesDeBacktracking {

	/**
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		try {
			int numero = Integer.parseInt( sc.nextLine() );
			
			partesConj1( new int[numero] );
			
			partesConj2( new int[numero] );
			
		} catch(Exception e){
			;
		}
	}
	
	/**
	 * 
	 * @param c
	 */
	private static void partesConj1(int[] c) {
		boolean[] subc = new boolean[c.length];
		partes1(c.length, 0, c, subc);
	}

	/**
	 * 
	 * @param c
	 * @param v
	 */
	private static void imprimir(int[] c, boolean[] v) {
		for (int i = 0; i < v.length; i++)
			if (v[i])
				System.out.print(c[i] + " ");
		System.out.println();
	}

	/**
	 * 
	 * @param n
	 * @param i
	 * @param c
	 * @param subc
	 */
	private static void partes1(int n, int i, int[] c, boolean[] subc) {
		for (int k = 0; k <= 1; k++) {
			if (k == 0)
				subc[i] = false;
			else
				subc[i] = true;
			if (i == n - 1)
				imprimir(c, subc);
			else
				partes1(n, i + 1, c, subc);
		}
	}

	// ////////////////////////////////////////////////////////////////////////
	// ///////////////////////////////////////////////////////////////////////
	// //////////////////////////////////////////////////////////////////////

	/**
	 * 
	 * @param c
	 */
	private static void partesConj2(int[] c) {
		int[] subc = new int[c.length];
		partes2(c.length, 0, -1, c, subc);
	}

	/**
	 * 
	 * @param c
	 * @param subc
	 * @param fin
	 */
	private static void imprimir(int[] c, int[] subc, int fin) {
		for (int i = 0; i <= fin; i++)
			System.out.print(c[subc[i]] + " ");
		System.out.println();
	}

	/**
	 * 
	 * @param n
	 * @param i
	 * @param j
	 * @param c
	 * @param subc
	 */
	private static void partes2(int n, int i, int j, int[] c, int[] subc) {
		imprimir(c, subc, i - 1);

		for (int k = j + 1; k < n; k++) {
			subc[i] = c[k];

			partes2(n, i + 1, k, c, subc);
		}
	}

}
